package com.kevin.Code.Greedy;

import java.util.Arrays;

/**
 * @author Vinlee Xiao
 * @Classname GasStation
 * @Description Leetcode 134 加油站  贪心算法  中等难度 完全没啥思路
 * @Date 2021/9/30 16:33
 * @Version 1.0
 */
public class GasStation {

    /**
     * @param gas
     * @param cost
     * @return
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {

        boolean isValid = false;
        int len = gas.length;
        int preSum = 0;
        int totalSum = 0;
        //用来存储两个数之差
        int[] reminder = new int[len];
        Arrays.fill(reminder, 0);
        //index 索引下标

        //
        for (int i = 0; i < len; i++) {

            reminder[i] = gas[i] - cost[i];

            //汽车内含有的汽油多余0
            if (reminder[i] > 0 || (reminder[i] == 0 && gas[i] != 0)) {

                //用于记录该坐标之后的数据和
                totalSum = reminder[i];

                for (int j = i + 1; j < len; j++) {
                    totalSum = totalSum + gas[j] - cost[j];
                    if (totalSum < 0) {
                        isValid = true;
                        break;
                    }
                }

                if (totalSum + preSum >= 0 && !isValid) {

                    return i;
                }
                isValid = false;
            }
            //记录i之前的数据之和
            preSum = preSum + reminder[i];
        }


        return -1;
    }


    /**
     * @param gas
     * @param cost
     * @return
     */
    public int canCompleteCircuit1(int[] gas, int[] cost) {
        int minNum = Integer.MAX_VALUE;
        int index = 0;
        int totalSum = 0;

        for (int i = 0; i < gas.length; i++) {

            totalSum = totalSum + gas[i] - cost[i];

            if (totalSum < minNum) {
                index = i;
                minNum = totalSum;
            }
        }

        return totalSum < 0 ? -1 : gas[index] > cost[index] ? index : (index + 1) % gas.length;
    }

    public static void main(String[] args) {
        int[] gas = new int[]{1, 2, 3, 4, 5};
        int[] cost = new int[]{3, 4, 5, 1, 2};

        GasStation gasStation = new GasStation();
        int i = gasStation.canCompleteCircuit(gas, cost);
        System.out.println(i);
    }
}
